/**
 * 和三数之和类似
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  nums.sort((a, b) => {
    return a - b;
  });

  let l = nums.length,
    res = [];
  for (let i = 0; i < l - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    // 加上提前终止条件，减少循环次数。
    if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
    if (nums[i] + nums[l - 1] + nums[l - 2] + nums[l - 3] < target) continue;
    for (let j = i + 1; j < l - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;
      if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
      if (nums[i] + nums[j] + nums[l - 1] + nums[l - 2] < target) continue;
      let m = j + 1,
        n = l - 1;
      while (m < n) {
        let he = nums[i] + nums[j] + nums[m] + nums[n];
        if (he === target) {
          // push以后，可能还有其他的可能答案，不要break跳出本次循环
          res.push([nums[i], nums[j], nums[m], nums[n]]);
          while (m < n - 1 && nums[n] === nums[n - 1]) {
            n--;
          }
          while (m < n - 1 && nums[m] === nums[m + 1]) {
            m++;
          }
          n--;
          m++;
        } else if (he > target) {
          n--;
        } else {
          m++;
        }
      }
    }
  }
  return res;
};
